package com.example.algorithm.hot_topic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Backtracking {
    /*
    数组的全排列
    输入：[1,2,3]
    输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    */
    List<Integer> nums;
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        this.res = new ArrayList<>();
        this.nums = new ArrayList<>();
        for (int num : nums) {
            this.nums.add(num);
        }
        dfs(0);
        return res;
    }
    void dfs(int x) {
        if (x == nums.size() - 1) {
            res.add(new ArrayList<>(nums));  // 添加排列方案
            return;
        }
        for (int i = x; i < nums.size(); i++) {
            swap(i, x);              //将i元素固定在x
            dfs(x + 1);              //固定x+1
            swap(i, x);              // 回溯
        }
    }

    void swap(int a, int b) {
        int tmp = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, tmp);
    }

    /*
    无重复元素，可重复使用，等于target的组合
    输入: candidates = [2,3,5], target = 8
    输出: [[2,2,2,2],[2,3,3],[3,5]]
    */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> state = new ArrayList<>(); //状态（子集）
        Arrays.sort(candidates); //排序
        int start = 0; //起始点
        List<List<Integer>> res = new ArrayList<>(); // 结果（子集列表）
        backtrack(state, target, candidates, start, res);
        return res;
    }
    void backtrack(List<Integer> state, int target, int[] choices, int start, List<List<Integer>> res) {
        // 子集和等于targe记录
        if (target == 0) {
            res.add(new ArrayList<>(state));
            return;
        }

        for (int i = start; i < choices.length; i++) {
            //子集和超过 target ，直接结束
            if (target - choices[i] < 0) {
                break;
            }
            // 尝试选择
            state.add(choices[i]);
            //更新 target, start
            backtrack(state, target - choices[i], choices, i, res);
            // 回退：撤销选择
            state.remove(state.size() - 1);
        }
    }


    /*
    单词搜索
    输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
    输出：true
    */
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, words, i, j, 0))
                    return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k])
            return false;
        if (k == word.length - 1)
            return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}
